Section: Software

Scotch

Participants : François Pellegrini [corresponding member] , Sébastien Fourestier.

parallel graph partitioning, parallel static mapping, parallel sparse matrix block ordering, graph repartitioning, mesh partitioning.

Scotch (http://www.labri.fr/~pelegrin/scotch/ ) is a software package for parallel and sequential sparse matrix ordering, parallel and sequential graph partitioning, as well as sequential static mapping and remapping, without and with fixed vertices, and mesh and hypergraph partitioning.

The initial purpose of Scotch was to compute high-quality static mappings of valuated graphs representing parallel computations onto target architectures of arbitrary topologies. This allows the mapper to take into account the topology and heterogeneity of the target architecture in terms of processor speed and link bandwidth. This feature, which was meant for the NUMA machines of the 1980's, has not been widely used in the past because machines in the 1990's became UMA again thanks to hardware advances. Now, architectures become NUMA again, and these features are regaining popularity.

Version 5.0 of Scotch , released on August 2007, was the first version to comprise parallel routines. This extension, called PT-Scotch (for “Parallel Threaded Scotch ”), is based on a distributed memory model, and makes use of the MPI and, optionally, Posix thread APIs. Version 5.1 , released on September 2008, extended the parallel features of PT-Scotch , which can now compute graph partitions in parallel by means of a parallel recursive bipartitioning framework. Release 5.1.10 had made Scotch the first full 64-bit implementation of a general purpose graph partitioner.

Version 6.0 , released on December 2012, corresponding to the 20-year anniversary of Scotch , offers many new features: static mapping with fixed vertices, static remapping, and static remapping with fixed vertices. Several critical algorithms of the formerly sequential Scotch library can now run in a multi-threaded way. All of these features will be available for the parallel PT-Scotch library in the upcoming release 6.1 .

Scotch has been integrated in numerous third-party software, which indirectly contribute to its diffusion, e.g. OpenFOAM (fluid mechanics solver, OpenCFD ltd.), the Code_Aster Libre solver (thermal and mechanical analysis software developed by French state-owned electricity producer EDF), the Zoltan module of the Trilinos software (SANDIA Labs), the parallel linear system solvers MUMPS (ENSEEITH/IRIT, LIP and LaBRI), SuperLUDist (U.C. Berkeley), PaStiX (LaBRI) and HIPS (LaBRI), etc. Scotch is natively available in several Linux and Unix distributions, as well as on some vendors platform (SGI, etc).